#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<string>

using namespace std;

unsigned long long f[1010][1010];

int numDistinct(string s, string t) {
    int n = s.size(), m = t.size();
    if (n < m)   return 0;

    memset(f, 0, sizeof f);
    for (int i = 0; i <= n; i++)   f[i][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s[i - 1] == t[j - 1])
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
            else
                f[i][j] = f[i - 1][j];
        }
    return f[n][m];
}

